package com.example.demo.leetcode;

import java.util.HashMap;
import java.util.Map;

/**
 * 链接：<a href="https://leetcode.cn/problems/copy-list-with-random-pointer/description/?envType=study-plan-v2&envId=top-interview-150">https://leetcode.cn/problems/copy-list-with-random-pointer/description/?envType=study-plan-v2&envId=top-interview-150</a>
 */
public class _138_随机链表的复制 {

    public Node copyRandomList(Node head) {
        if (head == null) {
            return null;
        }
        Map<Node, Node> map = new HashMap<>();
        Node copy = copy(head, map);
        while (head != null) {
            Node node = map.get(head);
            Node random = map.get(head.random);
            node.random = random;

            head = head.next;
        }
        return copy;
    }


    public Node copy(Node node, Map<Node, Node> map) {
        Node newNode = new Node(node.val);
        map.put(node, newNode);
        if (node.next != null) {
            newNode.next = copy(node.next, map);
        }
        return newNode;
    }
}
